/*
Title:      Graph Algorithm
Author:     Alchemist
Date:       2011-10
Category:   Graph
Description:Shortest Path:                  Dijkstra, SPFA, Bell-Man Ford, Floyd
            Minimum Spinning Tree:          Kruskal, Prim
            Strongly Connected Components:  Tarjan
            Maximum Matching:               Hungary
			Flow Network:                   Dinic
*/
#define _CRT_SECURE_NO_DEPRECATE

#include <stdio.h>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <memory.h>
#include <assert.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <cmath>

#define fo(a,b,c) for( a = ( b ); a < ( c ); ++ a )
#define fr(a,b) fo( a, 0, ( b ) )
#define fi(a) fr( i, ( a ) )
#define fj(a) fr( j, ( a ) )
#define fk(a) fr( k, ( a ) )
#define mp make_pair
#define pb push_back
#define all(v) (v).begin( ), (v).end( )
#define _(a,b) memset( a, b, sizeof( a ) )
#define PI 3.1415926
using namespace std;
int ni() { int a; scanf( "%d", &a ); return a; }
double nf() { double a; scanf( "%lf", &a ); return a; }
char sbuf[100005]; string ns() { scanf( "%s", sbuf ); return sbuf; }
long long nll() { long long a; scanf( "%lld", &a ); return a; }

template <class T> void out( T a, T b ) { bool first = true; for( T i = a; i != b; ++ i ) { if( !first ) printf( " " ); first = false; cout << * i; } printf( "\n" ); }
template <class T> void outl( T a, T b ) { for( T i = a; i != b; ++ i ) { cout << * i << "\n"; } }
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef map<string,int> msi;

const int maxn = 1000;

struct Edge
{
    int w,u,v;
};
vector<pii> adj[maxn];
vector<Edge> edge;
int n,m;
int d[maxn];

void dijkstra(int start)
{
    priority_queue<pii> q;

    memset(d,0x7f,sizeof(d));

    q.push(mp(0,start));
    d[start] = 0;
    while(!q.empty())
    {
        pii p = q.top();
        int v = p.second;
        int e = -p.first;
        if(d[v] >= e)
        for(int i = 0; i < adj[v].size(); i ++)
        {
            int vd = adj[v][i].first;
            int ed = adj[v][i].second;
            if(e + ed < d[vd])
            {
                d[vd] = e + ed;
                q.push(mp(-d[vd], vd));
            }
        }
        q.pop();
    }
}

void spfa(int start)
{
    queue<int> q;

    memset(d,0x7f,sizeof(d));

    q.push(start);
    d[start] = 0;
    while(!q.empty())
    {
        int v = q.front();
        for(int i = 0; i < adj[v].size(); i ++)
        {
            int vd = adj[v][i].first;
            int ed = adj[v][i].second;
            if(d[v] + ed < d[vd])
            {
                d[vd] = ed + d[v];
                q.push(vd);
            }
        }
        q.pop();
    }
}

void bellman_ford(int start)
{
    memset(d,0x7f,sizeof(d));
    d[start] = 0;

    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < m; j ++)
            if(d[edge[j].u] + edge[j].w < d[edge[j].v])
                d[edge[j].v] = d[edge[j].u] + edge[j].w;

    for(int j = 0; j < m; j ++)
        if(d[edge[j].u] + edge[j].w < d[edge[j].v])
            cerr << "error! negative loop." << endl;
}

int dist[maxn][maxn] = {0};
void floyd()
{
    for(int k = 1; k <= n; k ++)
    for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
    {
        if(dist[i][k] + dist[k][j] < dist[i][j])
            dist[i][j] = dist[i][k] + dist[k][j];
    }
}

int mst;

void prim()
{
    priority_queue<pii> q;
    int d[maxn];
    bool intree[maxn];
    memset(d,0x7f,sizeof(d));
    memset(intree,0,sizeof(intree));

    q.push(mp(0,1));
    d[1] = 0;
    mst = 0;
    while(!q.empty())
    {
        pii p = q.top();
        int v = p.second;
        int e = -p.first;
        if(intree[v])
            continue;
        intree[v] = true;
        mst += e;
        for(int i = 0; i < adj[v].size(); i ++)
        {
            int vd = adj[v][i].first;
            int ed = adj[v][i].second;
            if(!intree[vd] && ed < d[vd])
            {
                d[vd] = ed;
                q.push(mp(-ed, vd));
            }
        }
        q.pop();
    }
}

int getroot(const int* link, int x)
{
    while(link[x] != 0)
        x = link[x];
    return x;
}

bool comp_edge(Edge a, Edge b)
{
    return (a.w < b.w);
}
void kruskal()
{
    int link[maxn] = {0};
    int es = 0;
    mst = 0;
    sort(edge.begin(),edge.end(), comp_edge);
    for(int i = 0; i < m ; i ++)
    {
        int a = getroot(link, edge[i].u);
        int b = getroot(link, edge[i].v);
        if(a == b)
            continue;
        else
        {
            a = link[b];
            es ++;
            mst += edge[i].w;
        }
        if(es == n - 1)
            break;
    }
}

int c[maxn][maxn] = {0};
int maxflow;

void dinic(int s,int t)
{
	int pre[maxn];
	int d[maxn];

	int v, vd, maxf;

	int q[maxn], head, tail;
	bool vis[maxn] = {0};
	head = 1;
	tail = 0;
	q[tail] = t;
	d[t] = 0;
	vis[t] = 1;
	while(tail < head)
	{
		v = q[tail];
		for(int i = 0; i < adj[v].size(); i ++)
			if(!vis[adj[v][i].first])
			{
				vis[adj[v][i].first] = 1;
				d[adj[v][i].first] = d[v] + 1;
				q[head ++] = adj[v][i].first;
			}
		tail ++;
	}

	//memset(flow,0,sizeof(flow));
    maxflow = 0;
    maxf = 0x7fffffff;

	v = s;
	while(d[s] < n)
	{
	    bool isc = 0;
        //cout << v << endl;
		for(int i = 0; i < adj[v].size(); i ++)
		{
			vd = adj[v][i].first;
			//cout << vd << endl;
			if(c[v][vd] > 0 && d[v] == d[vd] + 1)
			{
				maxf = min(c[v][vd], maxf);
				pre[vd] = v;
				v = vd;
				if(v == t)
				{
                    while(v != s)
					{
						c[pre[v]][v] -= maxf;
						c[v][pre[v]] += maxf;
						v = pre[v];
					}
					maxflow += maxf;
					maxf = 0x7fffffff;
				}
				isc = 1;
				break;
			}
		}
        if(isc)
            continue;
		int mind = 0x7fffffff;
		for(int i = 0; i < adj[v].size(); i ++)
		{
			vd = adj[v][i].first;
			if(c[v][vd] > 0)
				mind = min(mind, d[vd] + 1);
		}

		if(mind < 0x7fffffff)
		{
			d[v] = mind;
		}
		else
		{
			d[v] = n;
			v = pre[v];
		}
	}
}

int mat[maxn];
bool used[maxn] = {0};
int match;

bool crosspath(int x)
{
	for(int i = 0; i < adj[x].size(); i ++)
	{
		int j = adj[x][i].first;
		if(!used[j])
		{
			used[j] = true;
			if(mat[j] == 0 || crosspath(mat[j]))
			{
				mat[j] = x;
				return true;
			}
		}
	}
	return false;
}

void hungary()
{
	match = 0;
	memset(mat,0,sizeof(mat));
	for(int i = 1; i <= n; i ++)
	{
		if(crosspath(i))
			match ++;
		memset(used,0,sizeof(used));
	}
}

int DFN[maxn];
int LOW[maxn];
bool instack[maxn];
int sta[maxn],sn;
int belong[maxn],bn;
int dindex;

void tarjan(int v)
{
    //cout << v << endl;
    int j;
	DFN[v] = sta[v] = ++ dindex;
	instack[v] = true;
    sta[++sn] = v;

	for(int  i = 0; i < adj[v].size(); i ++)
	{
	    j = adj[v][i].first;
		if(!DFN[j])
		{
		    tarjan(j);
		    if(LOW[j] < LOW[v])
                LOW[v] = LOW[j];
		}
		else if(instack[j] && DFN[j] < LOW[v])
            LOW[v] = DFN[j];
	}
	if(DFN[v] == LOW[v])
	{
	    bn ++;
	    do
	    {
	        j = sta[sn --];
	        instack[j] = false;
	        belong[j] = bn;
	    }while(j != v);
	}
}

void solve_scc()
{
    dindex = sn = bn = 0;
    memset(DFN,0,sizeof(DFN));
    for(int i = 1; i <= n; i ++)
        if(!DFN[i])
            tarjan(i);
}

/* main */
void init()
{
    ifstream fin("input.txt");
    fin >> n >> m;
    memset(dist,0x2f,sizeof(dist));
    for(int i = 1; i <= n ; i ++)
        dist[i][i] = 0;

    for(int i = 0; i < m ; i ++)
    {
        int u,v,w;
        fin >> u >> v >> w;
        adj[u].pb(mp(v,w));
        adj[v].pb(mp(u,w));
        dist[u][v] = dist[v][u] = w;
        Edge e;
        e.u = u;
        e.v = v;
        e.w = w;
        c[u][v] = c[v][u] = w;
        edge.pb(e);
    }
}

void output()
{
    cout << "Distance:" << endl;
    for(int i = 1; i <= n ; i ++)
        cout << d[i] << ' ';
    cout << endl;
}

void test_shortpath()
{
    dijkstra(1);
    output();
    spfa(1);
    output();
    bellman_ford(1);
    output();
    floyd();
    cout << "Distance:" << endl;
    for(int i = 1; i <= n ; i ++)
        cout << dist[1][i] << ' ';
    cout << endl;

}

void test_netflow()
{
    dinic(1,5);
    cout << "Max Flow:" << endl;
    cout << maxflow << endl;
}

void test_scc()
{
    solve_scc();
    cout << "Strongly Connected Components:" << endl;
    for(int i = 1; i <= n; i ++)
    {
        cout << belong[i] << ' ';
    }
}

int main()
{
    init();
    ofstream fout("output.txt");
    test_shortpath();
    test_netflow();
    test_scc();

    return 0;
}
